package org.lan.interview.mock;

import java.util.Arrays;

/**
 * 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
 * <p>
 * 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
 * <p>
 * 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：{{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}}
 * 输出：3
 * 解释：
 * 有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
 * 示例 2：
 * <p>
 * 输入：{{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}}
 * 输出：0
 * 解释：
 * 所有 1 都在边界上或可以到达边界。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= A.length <= 500
 * 1 <= A{i}.length <= 500
 * 0 <= A{i}{j} <= 1
 * 所有行的大小都相同
 *
 * @author <p><a href="mailto:1728209643@qq.com">XiaoSan</a>
 * @date 2019/11/19 9:27 AM
 */
public class Mock_001 {

    public static void main(String[] args) {
        int[][] A = {{0, 0, 0, 1, 1, 1, 0, 1, 0, 0}, {1, 1, 0, 0, 0, 1, 0, 1, 1, 1}, {0, 0, 0, 1, 1, 1, 0, 1, 0, 0}, {0, 1, 1, 0, 0, 0, 1, 0, 1, 0}, {0, 1, 1, 1, 1, 1, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 1, 1, 0, 1}, {0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, {0, 0, 1, 0, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 0, 0, 0, 1}};
        System.out.println(Arrays.deepToString(A));
        System.out.println(new Mock_001().numEnclaves(A));
    }

    public int numEnclaves(int[][] A) {
        int count = 0;
        int cLen = A[0].length;
        int rLen = A.length;
        for (int i = 0; i < rLen; i++) {
            if (A[i][0] == 1) {
                find(i, 0, A, rLen, cLen);
            }
            if (A[i][cLen - 1] == 1) {
                find(i, cLen - 1, A, rLen, cLen);
            }
        }
        for (int i = 0; i < cLen; i++) {
            if (A[0][i] == 1) {
                find(0, i, A, rLen, cLen);
            }
            if (A[rLen - 1][i] == 1) {
                find(rLen - 1, i, A, rLen, cLen);
            }
        }
        for (int i = 1; i < rLen - 1; i++) {
            for (int j = 1; j < cLen - 1; j++) {
                if (A[i][j] == 1) {
                    count++;
                }
            }
        }
        print(A);

        return count;
    }

    private void find(int x, int y, int[][] A, int rLen, int cLen) {
        if (A[x][y] == 1) {
            A[x][y] = 2;
            if (x - 1 > -1) {
                find(x - 1, y, A, rLen, cLen);
            }
            if (x + 1 < rLen) {
                find(x + 1, y, A, rLen, cLen);
            }
            if (y - 1 > -1) {
                find(x, y - 1, A, rLen, cLen);
            }
            if (y + 1 < cLen) {
                find(x, y + 1, A, rLen, cLen);
            }
        }
    }

    private static void print(int[][] arr) {
        for (int[] a : arr) {
            System.out.println(Arrays.toString(a));
        }
    }
}
